package com.likou;

import java.util.HashSet;
import java.util.Set;

public class q208 {

    class Trie {
        private Trie[] children;
        private boolean isEnd;


        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char charAt = word.charAt(i);
                int index = charAt - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            if (node == null) {
                return false;
            }
            if (node.isEnd) {
                return true;
            }
            return false;
        }

        public boolean startsWith(String prefix) {
            Trie node = searchPrefix(prefix);
            if (node == null) {
                return false;
            }
            return true;
        }

        private Trie searchPrefix(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                char charAt = prefix.charAt(i);
                int index = charAt - 'a';
                if (node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            }

            return node;
        }
    }


//    class Trie {
//
//        private Set<String> set;
//
//        public Trie() {
//            set = new HashSet<>();
//        }
//
//        public void insert(String word) {
//            set.add(word);
//        }
//
//        public boolean search(String word) {
//            return set.contains(word);
//        }
//
//        public boolean startsWith(String prefix) {
//            int l = prefix.length();
//            for (String s : set) {
//                if (l <= s.length()) {
//                    if (prefix.equals(s.substring(0, l))) {
//                        return true;
//                    }
//                }
//            }
//
//            return false;
//        }
//    }
}
